function TreeNode(val, left, right) {
  this.val = val == undefined ? 0 : val;
  this.left = left == undefined ? null : left;
  this.right = right == undefined ? null : right;
}

function buildTree(arr) {
  if (arr.length == 0) return null;

  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  while (i < arr.length) {
    const current = queue.shift();
    console.log("current:", current);
    if (arr[i] !== null) {
      current.left = new TreeNode(arr[i]);
      queue.push(current.left);
    }
    i++;
    if (i < arr.length && arr[i] !== null) {
      current.right = new TreeNode(arr[i]);
      queue.push(current.right);
    }
    i++;
  }
  return root;
}

// 翻转二叉树的函数
function invertTree(root) {
  if (root === null) {
    return null;
  }

  // 递归翻转左子树
  const left = invertTree(root.left);

  // 递归翻转右子树
  const right = invertTree(root.right);

  // 交换左右子树
  root.left = right;
  root.right = left;

  // 返回当前节点
  return root;
}

// 辅助函数：将二叉树转换为层序遍历数组
function treeToArray(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    if (current) {
      result.push(current.val);
      queue.push(current.left);
      queue.push(current.right);
    } else {
      result.push(null);
    }
  }

  // 去掉尾部多余的 null
  while (result[result.length - 1] === null) {
    result.pop();
  }

  return result;
}

const input = [4, 2, 7, 1, 3, 6, 9];
const root = buildTree(input);

console.log("原始二叉树：", treeToArray(root));

const invertedRoot = invertTree(root);
console.log("翻转后的二叉树：", treeToArray(invertedRoot)); 
